#include <iostream>
#include <cmath>
#include <ctime>
#include <iomanip>
#include "sorting.h"
using namespace std;

double generateVectorOfOrderP(const int &N, vector<int> &a, const double &P);

double testHeapSortingTime(const vector<int> &a);

double testQuickSortingTime(const vector<int> &a);

double testAdvancedQuickSortingTime(const vector<int> &a);

int main(int argc, char const *argv[])
{
    vector<int> vec{};
    for (int N : {1e5,2e5,4e5})
    {
        cout << "When N = " << N<<"\n";
        for (double P : {0.01, 0.10, 0.90,0.99})
        {
            double exactP = generateVectorOfOrderP(N, vec, P);
            cout << "For  P = "<< setprecision(4)<< exactP<<", ";
            cout << "HeapSort: " << setprecision(6)<< testHeapSortingTime(vec)<<"s,\t";
            cout << "QuickSort: " << setprecision(6)<< testQuickSortingTime(vec)<<"s,\t";
            cout << "AdvancedQuickSort: " << setprecision(6)<< testAdvancedQuickSortingTime(vec)<<"s.\n";
        }
    }
    return 0;
}

double testHeapSortingTime(const vector<int> &a)
{
    vector<int> a_copy;
    a_copy = a;
    clock_t t0,t1;
    t0 = clock();
    heapsort<int>(a_copy);
    t1 = clock();
    return (double)(t1-t0)/CLOCKS_PER_SEC;
}

double testQuickSortingTime(const vector<int> &a)
{
    vector<int> a_copy;
    a_copy = a;
    clock_t t0,t1;
    t0 = clock();
    quicksort<int>(a_copy);
    t1 = clock();
    return (double)(t1-t0)/CLOCKS_PER_SEC;
}

double testAdvancedQuickSortingTime(const vector<int> &a)
{
    vector<int> a_copy;
    a_copy = a;
    clock_t t0,t1;
    t0 = clock();
    AdvancedQuicksort<int>(a_copy);
    t1 = clock();
    return (double)(t1-t0)/CLOCKS_PER_SEC;
}

double generateVectorOfOrderP(const int &N, vector<int> &a, const double &P)
{
    int num = floor(sqrt(P) * N);
    const double P1 = 1.0 * num / N * (num - 1) / (N - 1);
    const double P2 = 1.0 * (num) / N * (num + 1) / (N - 1);
    double exactP = P1;
    if (abs(P1 - P) > abs(P2 - P))
    {
        num++;
        exactP = P2;
    }
    a.resize(N);
    for (int i = 0; i < N; i++)
    {
        for (; i < N - num; i++)
            a[i] = N - i;
        a[i] = i + 1 - N + num;
    }
    return exactP;
};
